package datastructure.tree;

/**
 * find the 'next' node (ie., in-order succesor) in binary search tree
 * 
 * @author Lei
 */
public class GetNextNodeInBST {

    public static TreeNode getNextNodeInBST(TreeNode node) {
        if (node.right != null) {
            return GetLeftMostChild.getLeftMostChild(node.right);
        }
        else {
            while (node.parent != null) {
                TreeNode parent = node.parent;
                if (node == parent.left) {
                    return parent;
                }
                else {
                    node = parent;
                }
            }
            return null;
        }
    }
    
    public static void main(String[] args) {
        
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n4 = new TreeNode(4);
        TreeNode n3 = new TreeNode(3);
        
        n2.left = n1;
        n1.parent = n2;
        
        n2.right = n4;
        n4.parent = n2;
        
        n4.left = n3;
        n3.parent = n4;
        
        System.out.println( GetNextNodeInBST.getNextNodeInBST(n2) );
        
    }
    
    
}
